/*
 * Dear diary,
 * This file contains implementations of various algorithms and
 * data structures.
 *
 * All implementations are type-independent and ANSI C compilant. (not true ATM)
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include <string.h>
#include <limits.h>

#include "alg.h"

/* {{{ memory allocation wrappers */
extern char *
s_calloc(size_t n, size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): calloc %lu times %lu bytes (tot %.4f MiB)\n",
			__func__, n, size, ((float) n * size) / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = calloc(n, size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, n * size);
		abort();
	}
	return ptr;
}

extern char *
s_malloc(size_t size)
{
	void *ptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): malloc %lu bytes (%.4f MiB)\n",
			__func__, size, (float) size / (1024.0f * 1024.0f));
#endif /* MEMDEBUG */
	ptr = malloc(size);
	if (ptr == NULL) {
		fprintf(stderr, "%s(): out of memory, failed to allocate %lu bytes\n",
				__func__, size);
		abort();
	}
	return ptr;
}

extern char *
s_realloc(char *oldptr, size_t newsize)
{
	void *newptr;
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): realloc oldptr %p for new size of %lu (%.4f MiB)\n",
			__func__, oldptr, newsize, (float) newsize / (1024.0f * 1024.0f));
#endif
	newptr = realloc(oldptr, newsize);
	if (newptr == NULL) {
		fprintf(stderr, "%s(): out of memory, "
				"failed to realloc %p for new size of %lu bytes\n",
				__func__, oldptr, newsize);
		abort();
	}
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): newptr %p\n", __func__, newptr);
#endif /* MEMDEBUG */
	return newptr;
}

void
s_free(void *ptr)
{
#ifdef MEMDEBUG
	fprintf(stderr, "%s(): freeing %p\n", __func__, ptr);
#endif
	free(ptr);
}
/* }}} */

/* {{{ queue */
extern struct queue *
queue__new(const int n, const size_t elem_size)
{
	struct queue *q = NULL;

	assert(n >= 1);
	assert(elem_size > 0);

	q = (struct queue *) s_malloc(sizeof *q);
	q->data = (char *) s_calloc(n, elem_size);
	q->_data_size = elem_size;
	q->head = 0;
	q->n = 0;
	q->_max = n;

	return q;
}

extern int
queue__push(struct queue *q, const void *p)
{
	assert(q != NULL);
	assert(p != NULL);

	if (q->n >= q->_max) {
		#ifdef QUEUE_DEBUG
		fprintf(stderr, "%s(): q->n (%d) >= q->_max (%d), can't push any deeper :-(\n",
				__func__, q->n, q->_max);
		#endif /* QUEUE_DEBUG */
		return -1;
	}

	memcpy(q->data + ((q->head + q->n++) % q->_max) * q->_data_size, p, q->_data_size);
	#ifdef QUEUE_DEBUG
	fprintf(stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n);
	#endif /* QUEUE_DEBUG */

	return 0;
}

extern int
queue__pop(struct queue *q, void *buf)
{
	assert(q != NULL);
	assert(buf != NULL);

	memcpy(buf, q->data + (q->head) * q->_data_size, q->_data_size);
	q->head = (q->head + 1) % q->_max;
	q->n--;
	#ifdef QUEUE_BEBUG
	fprintf(stderr, "%s(): q->head=%d, q->n=%d\n",
			__func__, q->head, q->n);
	#endif /* QUEUE_DEBUG */

	return 0;
}

extern int
queue__cleanup(struct queue *q)
{
	S_assert(q != NULL);
	if (q == NULL)
		return -1;

	if (q->_max == 0 || q->data == NULL)
		return 1;

	s_free(q->data);
	q->data = NULL;
	s_free(q);

	return 0;
}
/* }}} */

/* {{{ stack */
/* }}} */

/* {{{ autoarray */
extern struct vector *
vector__new(size_t elem_size, int p)
{
	struct vector *v = NULL;

	if (p < 0)
		p = 0;

	v = (struct vector *) s_malloc(sizeof *v);
	v->_max = 1 << p;
	v->_elem_size = elem_size;
	v->n = 0;
	v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);

	return v;
}

extern int
vector__append(struct vector *v, const void *app)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max == 0) {
		/* weird input, fix it */
		ret |= 2;
		debug_fprintf((stderr, "%s(): v->_max is 0, which means that your "
					"autoarray (v=%p) is messed up. trying to fix this.\n",
					__func__, (void*) v));
		if (v->_elem_size == 0) {
			ret |= 4;
			fprintf(stderr, "%s(): can't fix this mess, bailing out (%d)\n",
					__func__, ret);
			return ret;
		} else {
			v->_max = 1;
			v->n = 0;
			v->data = (char *) s_calloc((size_t) v->_max, v->_elem_size);
		}
	}

	if (v->n + 1 >= v->_max) {
		v->data = (char *) s_realloc(v->data, v->_elem_size * (v->_max *= 2));
	}
	memcpy(v->data + (v->n++) * v->_elem_size, app, v->_elem_size);

	return ret;
}

extern char *
vector__get_by_idx(struct vector *v, const int idx)
{
	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (NULL)\n",
				__func__);
		return NULL;
	}

	if (v->_elem_size == 0) {
		fprintf(stderr, "%s(): whoah, looks like your vector is messed up big time (NULL)\n",
				__func__);
		return NULL;
	}

	if (idx < 0 || idx >= v->n) {
		fprintf(stderr, "%s(): index out of range %d (v->n=%d)\n",
				__func__, idx, v->n);
		return NULL;
	}

	return v->data + (idx) * v->_elem_size;
}

extern int
vector__cleanup(struct vector *v)
{
	int ret = 0;

	if (v == NULL) {
		fprintf(stderr, "%s(): received NULL ptr, not doing anything (-1)\n",
				__func__);
		return -1;
	}

	if (v->_max > 0) {
		v->_max = v->n = 0;
		s_free(v->data);
		v->data = NULL;
	} else {
		ret |= 1;
	}

	/* TODO: improve logic */
	debug_fprintf((stderr, "%s(): freeing v=%p\n", __func__, (void*) v));
	s_free(v);

	return ret;
}
/* }}} */

/* {{{ singly-linked list */
/* TODO: include sorting of a linked list */
/* }}} */

/* {{{ doubly-linked list */
/*
 * This function inserts one node pointed to by 'ins' _after_ 'node'.
 */
extern struct dll_node *
dll_insert(struct dll_node *node, struct dll_node *ins)
{
	assert(node != NULL);
	if (ins == NULL) {
		debug_fprintf((stderr, "dll_insert(): ins is NULL, not doing anything\n"));
		return node;
	}

	if (node->next) {
		assert(node->next->prev == node);
		node->next->prev = ins;
	}
	ins->next = node->next;
	ins->prev = node;
	node->next = ins;
	return ins;
}

/*
 * This function extracts 'node' from a doubly-linked list and returns pointer
 * to that node, pointers '->prev' and '->next' are not reset.
 *
 * If you really want to get rid of a node, call
 * 	free(dll_delete(unneeded_node));
 */
extern struct dll_node *
dll_delete(struct dll_node *node)
{
	if (!node) {
		debug_fprintf((stderr, "dll_delete(): received NULL ptr, wtf am i supposed to delete?\n"));
		return NULL;
	}

	if (node->prev) {
		assert(node->prev->next == node);
		node->prev->next = node->next;
	}
	if (node->next) {
		assert(node->next->prev == node);
		node->next->prev = node->prev;
	}

	return node;
}

/*
 * Merge-sort for doubly-linked list.
 *
 * TODO: work out the use of (*cmp)() function
 */
extern void
dll_mergesort(struct dll_node *head, int (*cmp)(const void *, const void *))
{
	struct dll_node *end, *mid;
	struct dll_node *sorted, *first, *second;
	struct dll_node *swap;

	if (head == NULL || head->next == NULL) /* lengths 0, 1 */
		return;

	end = mid = head;
	while (end && end->next && end->next->next) {
		end = end->next->next;
		mid = mid->next;
	}
	if (end && end->next) {
		end = end->next;
		mid = mid->next;
	}

	mid->prev->next = NULL;
	mid->prev = NULL;
	dll_mergesort(head, cmp);
	dll_mergesort(mid, cmp);

	if (cmp(head->data, mid->data) > 0) { /* this is the tricky part */
		char *t1;
		size_t t2;
		struct dll_node *t3;
		int t4;
#define SWAP_(a,b,t) do{(t)=(a),(a)=(b),(b)=(t);}while(0)
		if (head->next && mid->next)
			SWAP_(head->next->prev, mid->next->prev, t3);
		SWAP_(head->x, mid->x, t4);
		SWAP_(head->data, mid->data, t1);
		SWAP_(head->_data_size, mid->_data_size, t2);
		SWAP_(head->prev, mid->prev, t3);
		SWAP_(head->next, mid->next, t3);
#undef SWAP_
	}

	/*
	 * from now on using only ->prev and ->next pointers should suffice us
	 */
	first = head->next;
	if (first) first->prev = NULL;
	second = mid;

	sorted = head;
	sorted->next = NULL;
	assert(sorted->prev == NULL);

	while (first && second) {
		assert(sorted->next == NULL);

		/* TODO: un-copypaste this code (use 'swap' ptr) */
		if (cmp(first->data, second->data) < 0)
			swap = first;
		else
			swap = second;

		assert(swap->prev == NULL);

		sorted->next = swap;
		swap->prev = sorted;
		sorted = swap;

		swap = swap->next;
		if (swap) {
			assert(swap->prev == sorted);
			swap->prev->next = NULL;
			swap->prev = NULL;
		}
	}
	assert(sorted->next == NULL);
	if (first) {
		assert(first->prev == NULL);
		sorted->next = first;
		first->prev = sorted;
	}
	if (second) {
		assert(second->prev == NULL);
		sorted->next = second;
		second->prev = sorted;
	}
}
/* }}} */

/* {{{ mergesort (with copy array optimization) */
static void
mergesort__merge(void *p1, size_t nmemb, size_t size,
		int (*cmpf)(const void *, const void *),
		void *p2, const int depth,
		size_t L, size_t M, size_t R)
{
	register char *base, *cpybuf;
	size_t i = L, j = M + 1;
	register size_t s = 0; /* points to where we will place next element */

	if (depth & 1)
		base = p1, cpybuf = p2;
	else
		base = p2, cpybuf = p1;

	while (i <= M && j <= R) {
		if (cmpf(base + i * size, base + j * size) <= 0) {
			if (i <= M) {
				memcpy(cpybuf + s*size, base + i*size, size);
				s++;
				i++;
			} else if (j <= R) {
				memcpy(cpybuf + s*size, base + j*size, size);
				s++;
				j++;
			}
		} else {
			if (j <= R) {
				memcpy(cpybuf + s*size, base + j*size, size);
				s++;
				j++;
			} else if (i <= M) {
				memcpy(cpybuf + s*size, base + i*size, size);
				s++;
				i++;
			}
		}
	}

	/*
	 * let's see how this works
	 */
	while (i <= M)
		memcpy(cpybuf + (s++) * size, base + (i++) * size, size);
	while (j <= R)
		memcpy(cpybuf + (s++) * size, base + (j++) * size, size);
}

static void
mergesort__main(void *base, size_t nmemb, size_t size,
		int (*cmpf)(const void *, const void *),
		void *cpybuf, const int depth,
		size_t L, size_t R)
{
	size_t M = (L + R) / 2;

	if (L < R) {
		mergesort__main(base, nmemb, size, cmpf, cpybuf, depth + 1, L, M);
		mergesort__main(base, nmemb, size, cmpf, cpybuf, depth + 1, M + 1, R);
		mergesort__merge(base, nmemb, size, cmpf, cpybuf, depth, L, M, R);
	}
}

extern void
mergesort(void *base, size_t nmemb, size_t size,
		int (*cmpf)(const void *, const void *))
{
	void *cpybuf;

	cpybuf = s_malloc(nmemb * size);
	memcpy(cpybuf, base, nmemb * size);
	mergesort__main(base, nmemb, size, cmpf, cpybuf, 0,
			0UL, nmemb - 1UL);
	s_free(cpybuf);
}
/* }}} */

/* {{{ priority queue */
/* {{{ heap mng */
/*
 * TODO: generalize these functions
 */
static int
pqueue__heap_sift_down(struct pqueue *pq, int idx)
{
	register int swap;
	int parent = idx, child;

	while (parent * 2 + 1 < pq->n) {
		child = parent * 2 + 1;
		swap = parent;

		if ((*pq->cmp)(pq->data + (parent) * pq->_data_size,
		               pq->data + (child) * pq->_data_size) > 0) {
			swap = child;
		}

		if (child + 1 < pq->n &&
		    (*pq->cmp)(pq->data + (swap) * pq->_data_size,
		               pq->data + (child + 1) * pq->_data_size) > 0) {
			swap = child + 1;
		}

		if (swap != parent) {
#ifdef DEBUG
			char *_bytes = bytes_to_str(pq->data + (parent) * pq->_data_size,
										pq->_data_size);
			fprintf(stderr, "%s(): swapping (%s) with ", __func__, _bytes);
			s_free(_bytes);
			_bytes = bytes_to_str(pq->data + (swap) * pq->_data_size,
							pq->_data_size);
			fprintf(stderr, "(%s)\n", _bytes);
			s_free(_bytes);
#endif
			memmove(pq->data + (pq->n) * pq->_data_size,
					pq->data + (parent) * pq->_data_size,
					pq->_data_size);
			memmove(pq->data + (parent) * pq->_data_size,
					pq->data + (swap) * pq->_data_size,
					pq->_data_size);
			memmove(pq->data + (swap) * pq->_data_size,
					pq->data + (pq->n) * pq->_data_size,
					pq->_data_size);
			parent = swap;
		} else {
			return 1;
		}
	}

	return 2;
}

static int
pqueue__heap_sift_up(struct pqueue *pq, int idx)
{
	int child = idx, parent = (idx - 1) / 2;

	while (child > 0) {
		if ((*pq->cmp)(pq->data + (parent) * pq->_data_size,
						pq->data + (child) * pq->_data_size) > 0) {
#ifdef DEBUG
			char *_bytes = bytes_to_str(pq->data + (parent) * pq->_data_size,
										pq->_data_size);
			fprintf(stderr, "%s(): swapping (%s) with ", __func__, _bytes);
			s_free(_bytes);
			_bytes = bytes_to_str(pq->data + (child) * pq->_data_size,
							pq->_data_size);
			fprintf(stderr, "(%s)\n", _bytes);
			s_free(_bytes);
#endif
			memmove(pq->data + (pq->n) * pq->_data_size,
					pq->data + (parent) * pq->_data_size,
					pq->_data_size);
			memmove(pq->data + (parent) * pq->_data_size,
					pq->data + (child) * pq->_data_size,
					pq->_data_size);
			memmove(pq->data + (child) * pq->_data_size,
					pq->data + (pq->n) * pq->_data_size,
					pq->_data_size);

			child = parent--;
			parent /= 2;
		} else {
			return 1;
		}
	}

	return 2;
}
/* }}} */
/*
 * Returns an initialized pqueue
 */
extern struct pqueue *
pqueue__new(const size_t elem_size, int exp, const bool autoexpand,
		int (*f)(const void *, const void *))
{
	struct pqueue *pq;

	/* if (f == NULL) f = &numcmp; default to integers */
	if (exp <= 0) exp = 6; /* default to 64 elements */
	S_assert(exp <= 23); /* 8,388,608 elements _might_ be a little too much */
	assert(elem_size != 0);

	pq = s_malloc(sizeof *pq);
	pq->data = s_calloc((pq->_max = 1<<exp), (pq->_data_size = elem_size));
	pq->n = 0;
	pq->cmp = f;
	pq->_autoexpand = autoexpand; /* TODO */

	return pq;
}

/*
 * Insert element that 'elem' points to into the pqueue.
 */
extern int
pqueue__insert(struct pqueue *pq, const void *elem)
{
	char *tmp = NULL;

	if (pq == NULL) {
		fprintf(stderr, "%s(): pq == NULL, not doing anything (-2)\n", __func__);
		return -2;
	}

	if (elem == NULL) {
		fprintf(stderr, "%s(): elem == NULL, what am i supposed to insert? (-1)\n", __func__);
		return -1;
	}

	if (pq->n + 1 >= pq->_max) {
		/* i betcha the ">=" makes you wonder .. */
		tmp = s_realloc(pq->data, (pq->_max <<= 1) * pq->_data_size);
		assert(tmp != NULL);
		pq->data = tmp;
	}
	memcpy(pq->data + (pq->_data_size * pq->n), elem, pq->_data_size);

	pqueue__heap_sift_up(pq, pq->n++);

	return 0;
}

/*
 * Extract the top element from the pqueue and put it into 'obuf' buffer.
 */
extern int
pqueue__extract(struct pqueue *pq, void *buf)
{
	if (pq == NULL) {
		fprintf(stderr, "%s(): received a NULL ptr, not doing anything (-1)\n", __func__);
		return -1;
	}

	if (buf != NULL)
		memcpy(buf, pq->data, pq->_data_size);
	memmove(pq->data, pq->data + (--pq->n) * pq->_data_size, pq->_data_size);
	pqueue__heap_sift_down(pq, 0);

	return 0;
}

extern int
pqueue__cleanup(struct pqueue *pq)
{
	if (pq == NULL) {
		fprintf(stderr, "%s(): received a NULL ptr, not doing anything (-1)\n", __func__);
		return -1;
	}

	if (pq->_max > 0) {
		s_free(pq->data);
		pq->data = NULL;
	}
	s_free(pq);

	return 0;
}
/* }}} */

/* {{{ graph repr: adjlist w/ doubly-linked list */
extern void
adjl_dll_connect(struct adjlist_dll *node, const int conid, const int edgeid)
{
	struct dll_node *Wilson;

	Wilson = (struct dll_node *) s_calloc(1, sizeof *Wilson);
	Wilson->x = conid;
	Wilson->y = edgeid;
	Wilson->prev = Wilson->next = NULL;

	if (node->head == NULL) {
		assert(node->tail == NULL);
		node->head = node->tail = Wilson;
		node->_list_len = 1;
	} else {
		node->tail = dll_insert(node->tail, Wilson);
		node->_list_len++;
	}
}

extern void
adjl_dll_cleanup(struct adjlist_dll *al)
{
	struct dll_node *nx = al->head, *pr = al->head;

	while (nx) {
		pr = nx;
		nx = nx->next;
		s_free(pr);
	}
	al->_list_len = 0;
	al->head = al->tail = NULL;
}
/* }}} */

/* {{{ union-find dataset */
void
uf__make_set(struct unionfind *uf, const int x)
{
	uf->parent[x] = x;
	uf->rank[x] = 0;
}

int
uf__find_set(struct unionfind *uf, const int x)
{
	if (x == uf->parent[x])
		return x;
	return uf->parent[x] = uf__find_set(uf, uf->parent[x]);
}

void
uf__union(struct unionfind *uf, int x, int y)
{
	x = uf__find_set(uf, x);
	y = uf__find_set(uf, y);
	if (x != y) {
		if (uf->rank[x] < uf->rank[y])
			SWAP_INT(x, y);
		uf->parent[y] = x;
		if (uf->rank[x] == uf->rank[y])
			uf->rank[x]++;
	}
}
/* }}} */

/* {{{ misc */
extern struct dll_node *
vector_to_dll_list(struct vector *v)
{
	struct dll_node *head = NULL, *tail = NULL;
	struct dll_node *next;
	register int i;

	if (v == NULL || v->_max == 0 || v->n == 0)
		return NULL;

	head = tail = s_calloc(1UL, sizeof *head);
	head->x = v->data[0];

	for (i = 1; i < v->n; i++) {
		next = s_calloc(1UL, sizeof *next);
		next->x = v->data[i];
		tail = dll_insert(tail, next);
	}

	return head;
}

extern char *
bytes_to_str(const void *ptr, const size_t size)
{
	char *str;
	const unsigned char *byte = ptr;
	int offset;

	/* each byte is represented as "0x??" and a
	 * whitespace character in between */
	str = s_malloc(5 * size + 1);
	for (offset = 0; offset < size; offset++) {
		sprintf(str + offset * 5, "0x%02hhx ", byte[offset]);
	}
	str[size * 5 - 1] = '\0';

	return str;
}
/* }}} */

/* {{{ KMP and friends */
extern unsigned *
z_function(const char *s)
{
	int i, l, r;
	unsigned *z;
	size_t len;

	assert(s != NULL);
	len = strlen(s);
	z = (unsigned *) s_calloc(len, sizeof *z);

	for (i = 1, l = 0, r = 0; i < len; ++i) {
		if (i <= r)
			z[i] = MIN(r - i + 1, z[i - l]);
		while (i + z[i] < len && s[z[i]] == s[i + z[i]])
			++z[i];
		if (i + z[i] - 1 > r)
			l = i, r = i + z[i] - 1;
	}

	return z;
}

extern unsigned *
prefix_function(const char *s)
{
	unsigned *p = NULL;
	register int i, j;
	size_t len;

	assert(s != NULL);
	len = strlen(s);
	p = (unsigned *) s_calloc(len, sizeof p[0]);

	p[0] = 0;
	i = 1; /* current char */
	j = 0; /* reference char */
	while (i < len) {
		while (j > 0 && s[j] != s[i]) {
			j = p[j - 1];
		}
		if (s[j] == s[i]) {
			j++;
		}
		p[i] = j;
		i++;
	}

	return p;
}

extern char *
kmp(const char *str, const char *sub, unsigned *pref, struct vector *ans)
{
	register unsigned m;
	int i, _t;
	bool free_pref = false;
	size_t len_s = 0UL, len_sub = 0UL;

	assert(str != NULL);
	assert(sub != NULL);

	len_s = strlen(str);
	len_sub = strlen(sub);

	if (pref == NULL) {
		pref = prefix_function(sub);
		#ifdef DEBUG
		fputs("pi_func: ", stderr);
		for (m = 0U; m < len_sub; m++)
			fprintf(stderr, "%d%c", pref[m], m + 1 == len_sub ? '\n' : ' ');
		#endif /* DEBUG */
		free_pref = true;
	}

	for (m = i = 0; i < len_s; i++) {
		while (m > 0 && sub[m] != str[i])
			m = pref[m - 1];
		if (sub[m] == str[i])
			m++;
		if (m == len_sub) {
			if (ans != NULL) {
				_t = i - m + 1;
				vector__append(ans, &_t);
				m = pref[m - 1];
			} else {
				return str + i - m + 1;
			}
		}
	}

	if (free_pref)
		s_free(pref);

	return NULL;
}
/* }}} */

/* {{{ simple search-tree-based set */
/* TODO: make this type-independent */
struct st_node *
set__add(struct st_node *root, char new_key)
{
	struct st_node *prev;

	if (root == NULL)
		return NULL; /* look out for this too */

	while (root) {
		prev = root;
		if (new_key > root->key)
			root = root->right;
		else
			root = root->left;
	}
	if (new_key > prev->key)
		root = prev->right = s_calloc(1UL, sizeof *root);
	else
		root = prev->left = s_calloc(1UL, sizeof *root);
	root->key = new_key;
	root->ptr = root->left = root->right = NULL;

	return root;
}

struct st_node *
set__seek(struct st_node *root, char key)
{
	while (root) {
		if (root->key == key)
			return root;
		else if (root->key > key)
			root = root->left;
		else
			root = root->right;
	}

	return NULL; /* ouch! ya gotta look out for that! */
}

void
print_set(struct st_node *st)
{
	if (st->left)
		print_set(st->left);
	fputc(st->key, stderr);
	if (st->right)
		print_set(st->right);
}

struct st_node *
set__far_right(struct st_node *list)
{
	struct st_node *r = list;
	while (r && r->right) r = r->right;
	return r;
}

struct st_node *
set__far_left(struct st_node *list)
{
	struct st_node *l = list;
	while (l && l->left) l = l->left;
	return l;
}

/*
 * Turn search-tree set into a linked list
 */
extern struct dll_node *
set__to_dll(struct st_node *set_root)
{
	/* TODO */
}
/* }}} */

/* {{{ aho-corasick */
int
ac__reg_word(struct ac_node *root, const char *w, const int id)
{
	register int i;
	struct st_node *next;

	i = 0;
	while (w[i]) {
		if (root->set == NULL) {
			/* this is a little ugly, but oh well.. */
			root->set = s_calloc(1UL, sizeof *root->set);
			root->set->key = w[i];
			root->set->ptr = s_calloc(1UL, sizeof *root);
			root->set->ptr->prev = root;
			root->leaf_count = 1;
		}

		if (next = set__seek(root->set, w[i]), next == NULL) {
			next = set__add(root->set, w[i]);
			next->ptr = s_calloc(1UL, sizeof *root);
			next->ptr->prev = root;
			root->leaf_count++;
		}
		root = next->ptr;
		i++;
	}
	root->final_pattern = true;
	root->pattern_id = id;
	root->pattern_len = i - 1;

	return 0;
}

static int
ac__count_nodes(struct ac_node *node, struct st_node *link)
{
	int count = 0;

	if (node != NULL && link == NULL) {
		count += 1;
		count += ac__count_nodes(NULL, node->set);
	} else if (node == NULL && link != NULL) {
		count += ac__count_nodes(NULL, link->left);
		count += ac__count_nodes(NULL, link->right);
		count += ac__count_nodes(link->ptr, NULL);
	}
	/* i didnt even know i could do that! */

	return count;
}

static void
ac__unroll_set(struct ac_node *node, struct st_node *link)
{
	static int index = 0; /* don't remove 'static'! */

	if (node != NULL && link == NULL) {
		S_assert(node->leaf == NULL);
		if (node->leaf_count == 0)
			return; /* apparently, this node really is a leaf,
			           nothing to do, exiting */

		/* This can potentially eat a lot of memory */
		node->leaf = s_calloc(node->leaf_count, sizeof *node->set);

		/* careful here.. */
		ac__unroll_set(node, node->set);
		index = 0;
	} else if (node != NULL && link != NULL) {
		/*
		 * If we somehow call ourself and second argument ends up
		 * being NULL, we're screwed!
		 */
		if (link->left)
			ac__unroll_set(node, link->left);

		node->leaf[index] = *link;
		index += 1;
		debug_fprintf((stderr, "%lx: node->leaf[%d] = \'%c\'\n",
					(long unsigned) &node, index - 1, link->key));

		if (link->right)
			ac__unroll_set(node, link->right);
	}
}

static void
ac__unroll_all_sets(struct ac_node *node)
{
	int i;

	ac__unroll_set(node, NULL);
	for (i = 0; i < node->leaf_count; i++)
		ac__unroll_all_sets(node->leaf[i].ptr);
}

extern int
ac__prefix_func(struct ac_node *acroot)
{
	struct queue *q;
	struct ac_node *nd, *nxt; /* current node in bfs */
	struct ac_node *pref; /* looks for suitable prefix function value */
	struct st_node *next_link;
	char c;
	register int i;

	ac__unroll_all_sets(acroot);
	q = queue__new(ac__count_nodes(acroot, NULL) - 1, sizeof acroot);
	queue__push(q, &acroot);
	acroot->prefix = acroot;
	S_assert(acroot->prev == acroot);
	acroot->prev = acroot;

	while (q->n) {
		queue__pop(q, &nd);

		for (i = 0; i < nd->leaf_count; i++) {
			nxt = nd->leaf[i].ptr;
			c   = nd->leaf[i].key;
			queue__push(q, &nxt);

			/*
			 * So in a situation like
			 *    p  -[c]-> v
			 * we traverse all p's prefix function values until we find
			 * a p* node that has the same -[c]-> edge. Therefore, we have
			 *    p* -[c]-> v*
			 * and v's prefix function will be the v* node.
			 *
			 * nd := p
			 * nxt := v
			 */
			/*
			 * Prefix function value for trie root and
			 * all its direct descendants is trie root.
			 */
			if (nd->root) {
				nxt->prefix = nxt->prev;
			} else {
				S_assert(nxt->prev == nd);

				pref = nd->prefix;
				while (!(next_link = set__seek(pref->set, c)) &&
						pref->root == false)
					pref = pref->prefix;
				nxt->prefix = next_link ? next_link->ptr : acroot;

				/* The "out" function. */
				if (nxt->prefix->final_pattern)
					nxt->out = nxt->prefix;
				else if (nxt->prefix->out && nxt->prefix->out->final_pattern)
					nxt->out = nxt->prefix->out;
				else {
					S_assert(nxt->out == NULL);
					nxt->out = NULL;
				}
			}
		}
	}

	queue__cleanup(q);
	return 0;
}

int
ac__contains(struct ac_node *ac_dfa, const char *text, void (*cb)(int, int))
{
	register struct ac_node *state = ac_dfa;
	struct st_node *link;
	int i = 0;
	int ans = 0;

	while (text[i]) {
		while (state != ac_dfa && !set__seek(state->set, text[i]))
			state = state->prefix;

		if (link = set__seek(state->set, text[i]), link != NULL)
			state = link->ptr;

		if (state->final_pattern) {
			(*cb)(i - state->pattern_len, state->pattern_id);
			ans++;
		}

		if (state->out) {
			struct ac_node *out_func_res = state->out;
			while (out_func_res) {
				(*cb)(i - out_func_res->pattern_len,
						out_func_res->pattern_id);
				ans++;
				out_func_res = out_func_res->out;
			}
		}
		i++;
	}

	return ans;
}

void
ac__cleanup(struct ac_node *node, struct st_node *link)
{
	if (node && !link) {
		if (node->set) {
#ifdef DEBUG
			fprintf(stderr, "%lx: node->set ~= <", &node);
			print_set(node->set);
			fprintf(stderr, ">\n");
#endif /* DEBUG */
			ac__cleanup(NULL, node->set);
		}
		if (node->leaf_count > 0)
			s_free(node->leaf);
		s_free(node);
	} else if (!node && link) {
		if (link->left)
			ac__cleanup(NULL, link->left);
		if (link->right)
			ac__cleanup(NULL, link->right);
		ac__cleanup(link->ptr, NULL);
		s_free(link);
	} else {
		fputs("pardon me?\n", stderr);
	}
}
/* }}} */

/* {{{ suffix tree */
/*
 * This one is a little messy.
 * Careless Programming Style.
 */
int
suftree__add_suffix(struct suftree *root, int shift, const int suffix)
{
	struct suftree_edge *E;
	int idx = root->string[shift] != '\n' ? root->string[shift] - 'a' : 'z' - 'a' + 1;

	assert(root->string);
	assert(root->string_len >= 1);

	if (root->string[suffix] == '\n')
		return 1;

	E = root->edges[idx];

	if (E != NULL) {
		/* found an existing edge => at least first chars match */
		int match_len = 1;
		while (root->string[shift + match_len] == root->string[E->lo + match_len] &&
				root->string[shift + match_len] &&
				root->string[E->lo + match_len] &&
				E->lo + match_len < E->hi) {
			match_len++;
		}

		if (match_len < E->hi - E->lo) {
			/* split the edge */
			struct suftree *M = s_calloc(1UL, sizeof *M);
			struct suftree_edge *R = s_calloc(1ul, sizeof *R);
			/* struct suftree_edge *N = s_calloc(1ul, sizeof *N); */

			/*
			 * Strike this. It works only for a particular case.
			 * WAIT! This work every time, because if we're here,
			 * then it means that we've found different chars and
			 * different char are, you know, different. This IS general
			 * case code. Oh well, too late now. One level of recursion
			 * more, nobody will notice. I guess, we'll save up on code
			 * size!

			 * create a 'remainder' edge *
			R->lo = E->lo + match_len;
			R->hi = E->hi;
			R->node = E->node;

			 * update the current edge *
			E->hi = E->lo + match_len;
			E->node = M;

			 * insert a mid-way node (connected to the current edge) *
			M->string = root->string;
			M->string_len = root->string_len;
			M->edges[root->string[R->lo] - 'a'] = R;

			 * append a new edge to the mid-way node *
			N->lo = shift + match_len;
			N->hi = root->string_len;
			M->edges[root->string[shift + match_len] - 'a'] = N;
			 */

			R->lo = E->lo + match_len;
			R->hi = E->hi;
			R->node = E->node;

			E->hi = R->lo; /* E->hi = E->lo + match_len; */
			E->node = M;

			M->string = root->string;
			M->string_len = root->string_len;
			M->suffix = -1;

			idx = root->string[R->lo] != '\n' ? root->string[R->lo] - 'a' : 'z' - 'a' + 1;
			M->edges[idx] = R;

			return suftree__add_suffix(M, shift + match_len, suffix);
		} else if (match_len == E->hi - E->lo) {
			/* full match up until the end of the edge */
			return suftree__add_suffix(E->node, shift + match_len, suffix);
		} else {
			/* Woah! Unbelieavable! */
			fprintf(stderr, "%s():%d: Unexpected error. root->string=\"%*s\" shift+match_len=%d\n", __func__, __LINE__,
					(int) root->string_len - 1, root->string, shift + match_len);
		}
	} else {
		/* create a new edge */
		E = root->edges[idx] = s_calloc(1UL, sizeof *root->edges[0]);

		E->lo = shift;
		E->hi = root->string_len;

		E->node = s_calloc(1UL, sizeof *E->node);
		E->node->string = root->string;
		E->node->string_len = root->string_len;
		E->node->suffix = suffix;
		E->node->final = true;
	}
	return 0;
}

struct suftree *
suftree__new(char *text)
{
	struct suftree *root;
	int i = 0;

	root = s_calloc(1UL, sizeof *root);
	root->string = text;
	root->string_len = strlen(text);
	root->root = true;
	root->suffix = -2;
	S_assert(root->string[root->string_len - 1] == '\n');

	while (i < root->string_len) {
		/* add every suffix of 'text' */
		suftree__add_suffix(root, i, i);
		i++;
	}

	return root;
}

int
suftree__contains(struct suftree *root, const char *p)
{
	register int i = 0;
	struct suftree_edge *edge = root->edges[p[i] - 'a'];
	int diff = edge ? edge->lo : -1;

	while (p[i] && edge) {
		S_assert(root != NULL);
		S_assert(edge->node != NULL);
		S_assert(diff != -1);

		while (i + diff < edge->hi && p[i] && p[i] == root->string[i + diff])
			i++;

		if (i + diff < edge->hi && p[i] && p[i] != root->string[i + diff]) {
			goto negative;
		} else if (!p[i]) {
			goto affirmative;
		} else if (i + diff == edge->hi) {
			root = edge->node;
			edge = root->edges[p[i] - 'a'];
			diff = edge ? edge->lo - i : -1;
		} else {
			fprintf(stderr,
			        "%s():%d: Unexpected error.\n"
			        "%s():%d: p = \"%s\", p + i = \"%s\", "
			        "i = %d, diff = %d, edge->lo = %d, "
			        "edge->hi = %d\n",
			        __func__, __LINE__, __func__, __LINE__,
			        p, p + i, i, diff, edge->lo, edge->hi);
		}
	}
	if (!edge && p[i])
		goto negative;

affirmative:
	return (!(0));
negative:
	return 0;
}

int
suftree__cleanup(struct suftree *root)
{
	int i;
	for (i = 0; i < sizeof root->edges / sizeof root->edges[0]; i++) {
		if (root->edges[i]) {
			suftree__cleanup(root->edges[i]->node);
			s_free(root->edges[i]);
		}
	}
	s_free(root);

	return 0;
}
/* }}} */
